public class Sort {
    //实现直接插入排序方法
    public static void insertSort(int[] array){
        //遍历非有序部分数组
        for(int i=1;i<array.length;i++){
            //取出非有序部分的第一个元素并向前逐个比对
            int tmp=array[i];
            int j=i-1;
            for(;j>=0;j--){
                if(tmp<array[j]){
                    //若该元素比前面某元素小，则某元素后移，该元素继续向前比对
                    array[j+1]=array[j];
                }else{
                    //相反若该元素比前面某元素大，则退出循环
                    break;
                }
                //内层循环结束说明已经为该元素找到合适位置，直接插入即可
                array[j+1]=tmp;
            }
        }
    }

    //实现希尔排序方法
    public static void shellSort(int[] array){
        //设定间隔增量gap
        int gap=array.length;
        while (gap > 1) {
            //每次循环缩小间隔增量
            gap/=2;
            //以间隔增量对数组进行分组插入排序
            shellSortChild(array,gap);
        }
    }

    //实现希尔排序的底层方法
    private static void shellSortChild(int[]array,int gap){
        //遍历非有序部分数组，i++表示对每组进行交替排序
        for(int i=gap;i<array.length;i++){
            //取出非有序部分的第一个元素并向前逐个比对
            int tmp=array[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(tmp<array[j]){
                    //若该元素比前面某元素小，则某元素后移，该元素继续向前比对
                    array[j+gap]=array[j];
                }else{
                    //相反若该元素比前面某元素大，则退出循环
                    break;
                }
                //内层循环结束说明已经为该元素找到合适位置，直接插入即可
                array[j+gap]=tmp;
            }
        }
    }

    //实现直接选择排序
    public static void selectSort(int[]array){
        //遍历非有序部分数组
        for(int i=0;i< array.length;i++){
            //默认最小值下标为起始下标
            int minIndex=i;
            //遍历剩余部分寻找最小值下标
            for(int j=i+1;j< array.length;j++){
                if(array[j]<array[i]){
                    minIndex=j;
                }
            }
            //循环结束证明已经找到最小值下标，与非有序部分起始位置交换
            int tmp=array[minIndex];
            array[minIndex]=array[i];
            array[i]=tmp;
        }
    }

    //实现堆排序

    //创建一个大根堆的方法
    public static void createMaxHeap(int[] array){
        //从最后一棵子树倒序调整
        for(int parent=((array.length-1-1)/2);parent>=0;parent--){
            //调用向下调整的底层方法
            maxSiftDown(array,parent,array.length-1);
        }
    }

    //创建大根堆时调用到的向下调整的底层方法
    private static void maxSiftDown(int[]array,int parent,int end){
        //默认子女中的最大值为左子女
        int child=2*parent+1;
        while(child<end){
            //判断右子女是否为二者中最大值
            if(child+1<end){
                if(array[child]<array[child+1]){
                    child++;
                }
            }
            if(array[parent]<array[child]){
                //子女节点中最大值大于双亲则进行交换调整
                int temp=array[parent];
                array[parent]=array[child];
                array[child]=temp;
                //向下迭代
                parent=child;
                child=2*parent+1;
            }else{
                //子女节点中最大值小于双亲说明该树已经为大根堆，无需向下调整，直接中断即可
                break;
            }
        }
    }

    //利用创建的大根堆实现堆排序
    public static void heapSort(int[]array){
        createMaxHeap(array);
        int end= array.length-1;
        while(end>0){
            //将堆顶元素和堆尾元素交换
            int temp=array[end];
            array[end]=array[0];
            array[0]=temp;
            //利用大根堆向下调整的方法
            maxSiftDown(array,0,end);
            end--;
        }
    }
}
